from typing import *


class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        ans = [0] * (n + 1)
        x, y = min(x, y), max(x, y)
        r = n - y
        for i in range(1, y):
            # A.起点在y左边，终点在y右侧
            # i从左往右走，经过y走到y右侧
            # ...i..x........y....
            # ......x.i......y....
            # 从i出发经过x,y比i直接到y近，此时y右侧跟着y一起减小了
            if y - i > abs(i - x) + 1:
                ans[y - i - 1] -= 1  # [i..y] 之间距离 小于[i..x,1,y]
                # y右侧所有的z [i..y..z..]都缩短了，最远y - i + r，差分索引是id = y - i + r + 1 处+1，由于存储差分的数组是在id - 1位置
                ans[y - i + r] += 1
                ans[abs(i - x)] += 1  # 从y - i 变成 abs(i - x) + 1
                ans[abs(i - x) + 1 + r] -= 1
            # B.起点终点在x，y中间
            if i > x and i < y and y - 1 - i > i - x + 2:
                # .....x...i....j....y....
                # 从i经过x，y到j，比i到j近的情况
                # 一般情况 .....xi......jy...这种肯定行，假设j最小为z
                # 一般情况 .....xi...z...y...随着z向左移动，iz之间距离减小ixyz之间距离增大
                # z - i > (i - x) + 1 + y - z
                # 2z > 2i + y - x + 1
                # z > i + (y - x + 1) // 2
                # z >= i + ceil((y - x + 1) // 2)
                # z >= i + (y - x + 1 + 1) // 2
                # z 最小就是 (y - x + 2) // 2 + i
                ans[(y - x + 2) // 2 + i - i - 1] -= 1  # 原本从i到z的距离没了
                ans[y - 1 - i + 1 - 1] += 1  # 一直到z = y - 1，距离就是y - 1 - i
                ans[i - x + 1 + 1 - 1] += 1  # 取而代之的是i到y-1的距离i - x + 1 + 1
                # 到i-x-y-z的距离
                ans[i - x + 1 + y - ((y - x + 2) // 2 + i) + 1 - 1] -= 1
        # C.起点在x左边终点在x，y之间
        # 从左往右走，经过y往回走到z
        # ....i...x.....z...y..
        # 从i到x到y返回z的情况
        z = (x + y + 2) // 2  # z - x > y - z + 1
        # 如果从x左侧枚举，那么[z..y]也要枚举
        # 代码倒着走，枚举从[z..y]之间到x，这么做x左边就是一个范围了
        l = x - 1  # 左边一共有l条路
        # ........x.....z.i.y..
        for i in range(z, y):
            ans[i - x - 1] -= 1  # x.....z.i这个距离没了
            # x左侧都没了，一直到i - x + l + 1补回差分，差分id = 长度-1
            ans[i - x + l] += 1
            ans[y - i] += 1  # 取而代之的是长度y - i + 1,ID= 长度-1是差分数组位置
            ans[y - i + 1 + l] -= 1  # 补回差分

        for i in range(1, n):
            ans[i] = ans[i - 1] + ans[i]
        return [(n - i - 1 + ans[i]) * 2 for i in range(n)]


class Solution:
    def countOfPairs(self, n: int, x: int, y: int) -> List[int]:
        ans = [0] * (n + 1)
        x, y = min(x, y), max(x, y)
        r = n - y
        for i in range(1, y):
            if y - i > abs(i - x) + 1:
                ans[y - i - 1] -= 1
                ans[y - i + r] += 1
                ans[abs(i - x)] += 1
                ans[abs(i - x) + 1 + r] -= 1
            if i > x and i < y and y - 1 - i > i - x + 2:
                ans[(y - x + 2) // 2 + i - i - 1] -= 1
                ans[y - 1 - i + 1 - 1] += 1
                ans[i - x + 1 + 1 - 1] += 1
                ans[i - x + 1 + y - ((y - x + 2) // 2 + i) + 1 - 1] -= 1
        z = (x + y + 2) // 2
        l = x - 1
        for i in range(z, y):
            ans[i - x - 1] -= 1
            ans[i - x + l] += 1
            ans[y - i] += 1
            ans[y - i + 1 + l] -= 1
        for i in range(1, n):
            ans[i] = ans[i - 1] + ans[i]
        return [(n - i - 1 + ans[i]) * 2 for i in range(n)]


s = Solution()
print(a := s.countOfPairs(8, 8, 1), b := [16, 16, 16, 8, 0, 0, 0, 0], a == b)
print(s.countOfPairs(7, 1, 7) == [14, 14, 14, 0, 0, 0, 0])
print(s.countOfPairs(n=3, x=1, y=3) == [6, 0, 0])
print(s.countOfPairs(4, 1, 1) == [6, 4, 2, 0])
print(s.countOfPairs(8, 4, 7) == [16, 16, 12, 8, 4, 0, 0, 0])
print(s.countOfPairs(6, 1, 5) == [12, 14, 4, 0, 0, 0])
